package chapter03_binaryTree;

import javax.management.remote.rmi._RMIConnection_Stub;

/**
 * 描述：
 *       二叉树结点间的最大距离
 *       m：遍历的过程返回每颗子树的高，根据子树的高求出子树的，求出每颗子树的最大距离，
 *      正解：一个头结点为h的二叉树的最大距离可能来自哪里，以下三种情况：
 *              1）来自左子树的最大距离
 *              2）来自右子树的最大距离
 *              3）来自左子树的高 + 1 + 右子树的高
 *      递归的过程中采用后序遍历，需要保存两个信息，一个是当前子树的高h，
 *      另一个是当前子树的最大距离d。可以将d作为返回值，h作为参数传递
 * @author hl
 * @date 2021/6/2 9:07
 */
public class MaxDistance {
    public static void main(String[] args) {
        SerialBinaryTree serialBinaryTree = new SerialBinaryTree();
        Node head = serialBinaryTree.reconByLevel("1!2!3!4!5!6!7!#!#!#!#!#!#!#!#!");
        MaxDistance maxDistance = new MaxDistance();
        int d = maxDistance.maxDistance2(head);
        System.out.println(d);
    }
    public int maxDistance(Node head){
        //记录当前子树的高
        int[] record = new int[1];
        return posOrder(head, record);
    }

    private int posOrder(Node head, int[] record) {
        if (head == null) {
            record[0] = 0;
            return 0;
        }
        int lMax = posOrder(head.left, record);
        int lh = record[0];
        int rMax = posOrder(head.right, record);
        int rh = record[0];
        int curNodeMax = lh + rh + 1;
        record[0] = Math.max(lh, rh) + 1;
        return Math.max(Math.max(lMax, rMax), curNodeMax);
    }

    public int maxDistance2(Node head){
        if (head == null) {
            return 0;
        }
        int[] res = new int[1];
        posOrder2(head, res);
        return res[0];
    }

    public int posOrder2(Node head, int[] res){
        if (head == null) {
            return 0;
        }
        int lh = posOrder2(head.left, res);
        int lMax = res[0];
        int rh = posOrder2(head.right, res);
        int rMax = res[0];
        int distance = lh + rh + 1;
        res[0] = Math.max(Math.max(lMax, rMax), distance);
        return Math.max(lh, rh) + 1;
    }

}
